Possible Bipartition
2020/5/27
問題概要
https://gyazo.com/43565c8c89a12df0a933e05fd8c9f7ff
1~Nまでの番号で割り振られた人達を、dislike[i]の[a, b]においてa, bがそれぞれ同じグループにならない形で2グループに分けることは可能かどうか判定せよ、という問題
解法
が、割り振り方によって2グループ分けの可否が異なることが分かった
例えばg1 = [1, 2], g2 = [3, 4]と2グループに振り分けられていた状態でdislikes = [[5, 6], [2, 5]]とあった場合、[5, 6]の5を先にg1に割り振ってg1 = [1, 2, 5], g2 = [3, 4, 6]となった状態だとdislikesの2つ目をクリアできない
一方、最初の割り振りが逆だと成功する
解説ACしたので以下にまとめる
問題としては、2部グラフかどうか判定せよというやつなので、その判定法に従って素直に実装すれば解ける
時間計算量：$ O(N+E)
$ E := dislikesの配列長
考え方は↓のような感じ。
https://gyazo.com/944dd29db1ef869a16938d2d184e14ab
最初↓を見て、この動画のコードをもとに自己整理したのが上図。
https://www.youtube.com/watch?v=hWFqtlbnQV8
code:solution.cpp
class Solution {
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
vector<int> groups(N, -1);
vector<vector<int>> adj(N, vector<int>());
for (vector<int>& d : dislikes) {
adj[d0-1].push_back(d1-1); adj[d1-1].push_back(d0-1); }
for (int i=0; i<N; i++) {
// dfsの引数であるgrpには、未初期化状態には初期値のグループ0を割り振る
if (groupsi == -1 && !dfs(adj, groups, i, 0)) return false; }
return true;
}
bool dfs(vector<vector<int>>& adj, vector<int>& groups, int i, int grp) {
if (groupsi == -1) groupsi = grp; else return groupsi == grp; if (!dfs(adj, groups, n, 1-grp)) return false;
}
return true;
}
};
TLE解答
code:solution.cpp
class Solution {
public:
int rx, ry;
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
if (N < 3 || dislikes.size() < 1) return true;
map<int, int> m;
for (vector<int> d : dislikes) {
}
return search(dislikes, m, 1);
}
bool search(vector<vector<int>>& dislikes, map<int, int>& m, int i) {
if (i >= dislikes.size()) return true;
int dx = dislikesi0, dy = dislikesi1; int rdx = root(m, dx), rdy = root(m, dy);
if (rdx == rdy) return false;
// グループ入れがどっち付かずの場合、両方に入れたパターンで分岐してさらに走査
if (rdx!=rx && rdx!=ry && rdy!=rx && rdy!=ry) {
map<int, int> ma = m, mb = m;
return search(dislikes, ma, i+1) | search(dislikes, mb, i+1);
}
if (rdx != rx && rdx != ry) mdx = (rdy == ry) ? rx : ry; else mdy = (rdx == ry) ? rx : ry; return search(dislikes, m, i+1);
}
int root(map<int, int>& m, int v) {
}
};